from typing import List, Set
from collections import defaultdict

from chernc.treediff.gumtree.matchers.configuration_options import ConfigurationOptions
from chernc.treediff.gumtree.matchers.gumtree_properties import GumtreeProperties
from chernc.treediff.gumtree.matchers.mapping_store import MappingStore
from chernc.treediff.gumtree.matchers.matcher import Matcher
from chernc.treediff.gumtree.matchers.optimal.zs.zs_matcher import ZsMatcher
from chernc.treediff.gumtree.matchers.similarity_metrics import SimilarityMetrics
from chernc.treediff.gumtree.tree.tree import TreeLike


class GreedyBottomUpMatcher(Matcher):
    DEFAULT_SIZE_THRESHOLD = 1000
    DEFAULT_SIM_THRESHOLD = 0.5

    def __init__(self) -> None:
        self.size_threshold: int = self.DEFAULT_SIZE_THRESHOLD
        self.sim_threshold: float = self.DEFAULT_SIM_THRESHOLD

    def configure(self, properties: 'GumtreeProperties') -> None:
        self.size_threshold: int = properties.try_configure(ConfigurationOptions.bu_minsize, self.size_threshold)
        self.sim_threshold: float = properties.try_configure(ConfigurationOptions.bu_minsim, self.sim_threshold)

    def match(self, src: TreeLike, dst: TreeLike, mappings: 'MappingStore') -> 'MappingStore':
        for t in src.post_order():
            if t.is_root():
                mappings.add_mapping(t, dst)
                self.last_chance_match(mappings, t, dst)
                break
            elif not (mappings.is_src_mapped(t) or t.is_leaf()):
                candidates = self.get_dst_candidates(mappings, t)
                best = None
                max_sim = -1.0
                for cand in candidates:
                    sim = SimilarityMetrics.dice_similarity(t, cand, mappings)
                    if sim > max_sim and sim >= self.sim_threshold:
                        max_sim = sim
                        best = cand

                if best is not None:
                    self.last_chance_match(mappings, t, best)
                    mappings.add_mapping(t, best)

        return mappings

    def get_dst_candidates(self, mappings: 'MappingStore', src: TreeLike) -> List[TreeLike]:
        seeds = []
        for c in src.get_descendants():
            if mappings.is_src_mapped(c):
                seeds.append(mappings.get_dst_for_src(c))

        candidates = []
        visited = set()
        for seed in seeds:
            while seed.get_parent() is not None:
                parent = seed.get_parent()
                if parent in visited:
                    break
                visited.add(parent)
                if parent.get_type() == src.get_type() and not (mappings.is_dst_mapped(parent) or parent.is_root()):
                    candidates.append(parent)
                seed = parent

        return candidates

    def last_chance_match(self, mappings: 'MappingStore', src: TreeLike, dst: TreeLike) -> None:
        if src.get_metrics().size < self.size_threshold or dst.get_metrics().size < self.size_threshold:
            m = ZsMatcher()
            zs_mappings = m.match(src, dst, MappingStore(src, dst))
            for candidate in zs_mappings:
                src_cand = candidate.src
                dst_cand = candidate.dst
                if mappings.is_mapping_allowed(src_cand, dst_cand):
                    mappings.add_mapping(src_cand, dst_cand)

    def get_size_threshold(self) -> int:
        return self.size_threshold

    def set_size_threshold(self, size_threshold: int) -> None:
        self.size_threshold = size_threshold

    def get_sim_threshold(self) -> float:
        return self.sim_threshold

    def set_sim_threshold(self, sim_threshold: float) -> None:
        self.sim_threshold = sim_threshold

    def get_applicable_options(self) -> Set['ConfigurationOptions']:
        return {ConfigurationOptions.bu_minsize, ConfigurationOptions.bu_minsim}
